The present invention relates to integrated circuit (IC) design, and more specifically, to parallel incremental global routing.
The fabrication of an IC (i.e., chip) includes a number of phases from the logic design to the physical implementation. Once a logic design has been developed, the placement of logic elements is followed by the routing of wires to interconnect the elements, as needed. Based on the timing requirements of the design and how well those requirements have been met, these design, place, and route processes can be performed iteratively to finalize the design for physical implementation. Parallel optimization of the design can be achieved using a multi-threaded approach by partitioning the design into logic clusters and operating on each of the threads independently. When design changes are made locally, within a given thread, those changes can affect the chip-level (i.e., global) placement and global routing in the entire chip. Thus, an update of global placement and routing must be performed to account for the effect of local routing changes. While the placement updates can be performed relatively efficiently, the process of performing global routing based on changes within each thread, in turn, and the associated cost of long locks can undercut the efficiency gains of multi-threaded processing.